package problems;

public class Euler072Stolen extends AbstractEuler {
	private static final int D_MAX = 1000000;
	private Integer[] fact = new Integer[D_MAX + 1]; //fact[i] contains something of i... not sure what.

	private void fillFact() {
		for (int i = 0; i <= D_MAX; i++) {
			fact[i] = 1;
		}
		
		for (int i = 2; i <= D_MAX; i++) {
			if (fact[i] == 1) {
				for (int k = 2*i; k <= D_MAX; k += i) {
					if (fact[k] == 1) {
						fact[k] = i;
					}
				}
			}
		}
	}
	
	@Override
	public Number calculate() {
		fillFact();
		
		// Sum phi(2) .. phi(D_MAX)
		long sumOfPhi = 0;
		for (int i = 2; i <= D_MAX; i++) {
			sumOfPhi += phi(i);
		}
		return sumOfPhi;
	}
	
	private int phi(int x) {
		if (x <= 1)	return 1;
		int f = fact[x];
		if (f == 1)	return x - 1;
		int fp = 1;
		while ((x /= f) % f == 0) {
			fp *= f;
		}
		return phi(x) * (f - 1) * fp;
	}


	@Override
	protected Number getCorrectAnswer() {
		return 303963552391L;
	}

}
